package code.oldCode.classic150;

import java.util.*;

/**
 * @author cuihaoran
 * @date 2025/1/15
 */
public class Classic150_graphBFS {

    /* 909. 蛇梯棋 */
    public int snakesAndLadders(int[][] board) {
        // 最短路，用BFS，第一个到的就是最短。用DFS的话需要遍历所有路径，效率低。
        // 注意，编号为 1 和 n^2 的方格上没有蛇或梯子
        int n = board.length;
        boolean[][] isVisited = new boolean[n][n];
        Deque<int[]> deque = new ArrayDeque<>();
        deque.addLast(new int[]{1, 0});
        isVisited[getGraphPos(1, n)[0]][getGraphPos(1, n)[1]] = true;
        while (!deque.isEmpty()) {
            int[] node = deque.pollFirst();
            int pos = node[0];
            int steps = node[1];
            if (pos == n * n)
                return steps;
            for (int i = 1; i <= 6; i++) {
                int nextPos = pos + i;
                if (nextPos > n * n)
                    break;
                int[] nextGraphPos = getGraphPos(nextPos, n);
                if (board[nextGraphPos[0]][nextGraphPos[1]] != -1) {
                    nextPos = board[nextGraphPos[0]][nextGraphPos[1]];
                    nextGraphPos = getGraphPos(nextPos, n);
                }
                if (!isVisited[nextGraphPos[0]][nextGraphPos[1]]) {
                    isVisited[nextGraphPos[0]][nextGraphPos[1]] = true;
                    deque.addLast(new int[]{nextPos, steps + 1});
                }
            }
        }
        return -1;
    }

    // 把序号转换为坐标，其实可以先把二维的图转换为一维，再处理
    private int[] getGraphPos(int pos, int n) {
        int x = n - 1 - ((pos - 1) / n);
        int y = ((pos - 1) / n) % 2 == 0 ? ((pos - 1) % n) : (n - 1 - ((pos - 1) % n));
        return new int[]{x, y};
    }

    /* 433. 最小基因变化 */
    public int minMutation(String startGene, String endGene, String[] bank) {
        // 同样是用BFS求图中的最短路
        int geneNum = bank.length;
        List<Integer>[] graph = new List[geneNum];
        boolean[] isVisited = new boolean[geneNum];
        Deque<int[]> deque = new ArrayDeque<>();
        for (int i = 0; i < geneNum; i++) {
            graph[i] = new ArrayList<>();
        }
        for (int i = 0; i < geneNum; i++) {
            for (int j = i + 1; j < geneNum; j++) {
                if (rightChange(bank[i], bank[j])) {
                    graph[i].add(j);
                    graph[j].add(i);
                }
            }
            if (rightChange(bank[i], startGene)) {
                isVisited[i] = true;
                deque.addLast(new int[]{i, 1});
            }
        }
        while (!deque.isEmpty()) {
            int[] node = deque.pollFirst();
            int gene = node[0];
            int steps = node[1];
            if (bank[gene].equals(endGene))
                return steps + 1;
            for (int i = 0; i < graph[gene].size(); i++) {
                int nextGene = graph[gene].get(i);
                if (!isVisited[nextGene]) {
                    isVisited[nextGene] = true;
                    deque.addLast(new int[]{nextGene, steps + 1});
                }
            }
        }

        return -1;
    }

    private boolean rightChange(String a, String b) {
        char[] c1 = a.toCharArray();
        char[] c2 = b.toCharArray();
        int len = c1.length;
        int changes = 0;
        for (int i = 0; i < len; i++) {
            if (c1[i] != c2[i])
                changes++;
            if (changes > 1)
                break;
        }
        return changes == 1;
    }

    /* 127. 单词接龙 */
    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        // 这道题以下解法与 433. 最小基因变化 基本一致，但效率低。
        int wordNum = wordList.size();
        List<Integer>[] graph = new List[wordNum];
        Deque<int[]> deque = new ArrayDeque<>();
        boolean[] isVisited = new boolean[wordNum];
        for (int i = 0; i < wordNum; i++) {
            graph[i] = new ArrayList<>();
        }
        for (int i = 0; i < wordNum; i++) {
            for (int j = i + 1; j < wordNum; j++) {
                if (rightChange_(wordList.get(i), wordList.get(j))) {
                    graph[i].add(j);
                    graph[j].add(i);
                }
            }
            // 差一个的加入队列
            if (rightChange_(beginWord, wordList.get(i))) {
                isVisited[i] = true;
                deque.addLast(new int[]{i, 1});
            }
        }
        while (!deque.isEmpty()) {
            int[] node = deque.pollFirst();
            int word = node[0];
            int steps = node[1];
            if (wordList.get(word).equals(endWord))
                return steps + 1;
            for (int i = 0; i < graph[word].size(); i++) {
                int nextWord = graph[word].get(i);
                if (!isVisited[nextWord]) {
                    isVisited[nextWord] = true;
                    deque.addLast(new int[]{nextWord, steps + 1});
                }
            }
        }
        return 0;
    }

    private boolean rightChange_(String a, String b) {
        char[] c1 = a.toCharArray();
        char[] c2 = b.toCharArray();
        int len = c1.length;
        int changes = 0;
        for (int i = 0; i < len; i++) {
            if (c1[i] != c2[i])
                changes++;
            if (changes > 1)
                break;
        }
        return changes == 1;
    }

    // 可以优化的地方是，使用HashSet存单词，尝试替换单词每个位置的字符，并在set里找，在图很大的情况下，这样比遍历图要快。
    public int ladderLength_(String beginWord, String endWord, List<String> wordList) {
        // 将 wordList 放入一个 Set，便于快速判断单词是否存在
        Set<String> wordSet = new HashSet<>(wordList);
        if (!wordSet.contains(endWord)) {
            return 0; // endWord 不在单词列表中
        }

        // 广度优先搜索队列
        Queue<String> queue = new LinkedList<>();
        queue.offer(beginWord);
        Set<String> visited = new HashSet<>();
        visited.add(beginWord);

        int steps = 1; // 初始步数

        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                String currentWord = queue.poll();
                // 尝试每个位置替换字符
                for (int j = 0; j < currentWord.length(); j++) {
                    char[] wordArray = currentWord.toCharArray();
                    char originalChar = wordArray[j];
                    for (char c = 'a'; c <= 'z'; c++) {
                        if (c == originalChar) continue;
                        wordArray[j] = c;
                        String nextWord = new String(wordArray);
                        // 如果找到目标单词
                        if (nextWord.equals(endWord)) {
                            return steps + 1;
                        }
                        // 如果是合法单词且未访问过
                        if (wordSet.contains(nextWord) && !visited.contains(nextWord)) {
                            visited.add(nextWord);
                            queue.offer(nextWord);
                        }
                    }
                }
            }
            steps++;
        }
        return 0; // 无法到达 endWord
    }

    /* 208. 实现 Trie (前缀树/字典树) */
    class TrieNode {
        TrieNode[] children;
        boolean isWord;

        public TrieNode() {
            isWord = false;
            children = new TrieNode[26];
        }
    }

    class Trie {

        TrieNode root;

        public Trie() {
            root = new TrieNode();
        }

        public void insert(String word) {
            char[] chars = word.toCharArray();
            TrieNode node = root;
            for (char aChar : chars) {
                int val = aChar - 'a';
                if (node.children[val] == null) {
                    node.children[val] = new TrieNode();
                }
                node = node.children[val];
            }
            node.isWord = true;
        }

        public boolean search(String word) {
            char[] chars = word.toCharArray();
            TrieNode node = root;
            for (char aChar : chars) {
                int val = aChar - 'a';
                if (node.children[val] == null)
                    return false;
                node = node.children[val];
            }
            return node.isWord;
        }

        public boolean startsWith(String prefix) {
            char[] chars = prefix.toCharArray();
            TrieNode node = root;
            for (char aChar : chars) {
                int val = aChar - 'a';
                if (node.children[val] == null)
                    return false;
                node = node.children[val];
            }
            return true;
        }
    }

    /* 211. 添加与搜索单词 - 数据结构设计 */
    static class WordDictionary {
        static class WordNode {
            WordNode[] chars;
            boolean isWord;

            public WordNode() {
                chars = new WordNode[26];
                isWord = false;
            }
        }

        WordNode root;

        public WordDictionary() {
            root = new WordNode();
        }

        public void addWord(String word) {
            char[] wordChars = word.toCharArray();
            WordNode node = root;
            for (char wordChar : wordChars) {
                int val = wordChar - 'a';
                if (node.chars[val] == null) {
                    node.chars[val] = new WordNode();
                }
                node = node.chars[val];
            }
            node.isWord = true;
        }

        public boolean search(String word) {
            // 尝试递归搜索
            return DFSSearch_modified(word, 0, root);
        }

        // 自己写的DFS，正常写法+特殊情况递归调用DFS，之后递归不要用新建的String！！！
        private boolean DFSSearch(String nowWord, WordNode rootNode) {
            WordNode node = rootNode;
            int wordLen = nowWord.length();
            for (int i = 0; i < wordLen; i++) {
                char nowChar = nowWord.charAt(i);
                int val = nowChar - 'a';
                if (nowChar == '.') {
                    for (int j = 0; j < 26; j++) {
                        boolean result = false;
                        if (node.chars[j] != null) {
                            result = DFSSearch(nowWord.substring(i + 1), node.chars[j]);
                        }
                        if (result)
                            return true;
                    }
                    return false;
                } else {
                    if (node.chars[val] == null) {
                        return false;
                    }
                    node = node.chars[val];
                }
            }
            return node.isWord;
        }

        // 优化过的，不用不同的String递归，用index
        private boolean DFSSearch_modified(String nowWord, int index, WordNode rootNode) {
            WordNode node = rootNode;
            int wordLen = nowWord.length();
            for (int i = index; i < wordLen; i++) {
                char nowChar = nowWord.charAt(i);
                int val = nowChar - 'a';
                if (nowChar == '.') {
                    for (int j = 0; j < 26; j++) {
                        boolean result = false;
                        if (node.chars[j] != null) {
                            result = DFSSearch_modified(nowWord, i + 1, node.chars[j]);
                        }
                        if (result)
                            return true;
                    }
                    return false;
                } else {
                    if (node.chars[val] == null) {
                        return false;
                    }
                    node = node.chars[val];
                }
            }
            return node.isWord;
        }

        // 别人思路写的DFS，每个字母递归调一个函数，这样就快很多？
        private boolean DFSSearch_DFS(String word, int index, WordNode rootNode) {
            int wordLen = word.length();
            if (index == wordLen)
                return rootNode.isWord;
            char c = word.charAt(index);
            if (c == '.') {
                for (int i = 0; i < 26; i++) {
                    boolean tempFlag = false;
                    if (rootNode.chars[i] != null) {
                        tempFlag = DFSSearch_DFS(word, index + 1, rootNode.chars[i]);
                    }
                    if (tempFlag)
                        return true;
                }
                return false;
            } else {
                int val = c - 'a';
                if (rootNode.chars[val] != null) {
                    return DFSSearch_DFS(word, index + 1, rootNode.chars[val]);
                } else
                    return false;
            }
        }
    }

    /* 212. 单词搜索 II */
    static class MapTrieNode {
        String s; // 与一般的字典树不同的地方，单词结尾部分有一个单词的String
        MapTrieNode[] children;
        boolean isEnd;

        public MapTrieNode() {
            children = new MapTrieNode[26];
            isEnd = false;
        }
    }

    static class MapTrie {
        MapTrieNode root;

        public MapTrie() {
            root = new MapTrieNode();
        }

        private void addWord(String word) {
            char[] wordChars = word.toCharArray();
            MapTrieNode node = root;
            for (char wordChar : wordChars) {
                int val = wordChar - 'a';
                if (node.children[val] == null)
                    node.children[val] = new MapTrieNode();
                node = node.children[val];
            }
            node.isEnd = true;
            node.s = word;
        }
    }

    public List<String> findWords(char[][] board, String[] words) {
        MapTrie mapTrie = new MapTrie();
        int m = board.length;
        int n = board[0].length;
        boolean[][] isVisited = new boolean[m][n];
        List<String> ans = new ArrayList<>();
        for (String word : words) {
            mapTrie.addWord(word);
        }
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                searchMap(mapTrie.root, i, j, board, isVisited, ans);
            }
        }
        return ans;
    }

    private void searchMap(MapTrieNode root, int i, int j, char[][] board, boolean[][] isVisited, List<String> ans) {
        // 如果越界，直接返回，如果被访问过了，返回
        if (i < 0 || i >= board.length || j < 0 || j >= board[0].length || isVisited[i][j])
            return;
        // 当前没找到，返回
        char c = board[i][j];
        int val = c - 'a';
        if (root.children[val] == null)
            return;

        // 访问当前节点
        isVisited[i][j] = true;
        // ! 如果找到了单词，添加到ans，isEnd设为false，防止重复单词，并且接着往后找
        root = root.children[val];
        if (root.isEnd) {
            ans.add(root.s);
            root.isEnd = false;
        }
        // 递归访问上下左右
        searchMap(root, i + 1, j, board, isVisited, ans);
        searchMap(root, i - 1, j, board, isVisited, ans);
        searchMap(root, i, j + 1, board, isVisited, ans);
        searchMap(root, i, j - 1, board, isVisited, ans);
        // 撤回访问
        isVisited[i][j] = false;
    }

    public static void main(String[] args) {
        Classic150_graphBFS c = new Classic150_graphBFS();
        // ["o","a","a","n"]
        // ["e","t","a","e"]
        // ["i","h","k","r"]
        // ["i","f","l","v"]
        char[][] boards = new char[][]{{'o', 'a', 'a', 'n'}, {'e', 't', 'a', 'e'}, {'i', 'h', 'k', 'r'}, {'i', 'f', 'l', 'v'}};
        String[] words = new String[]{"oath", "pea", "eat", "rain"};
        System.out.println(c.findWords(boards, words));
    }
}
